package _go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var c, res int

func kthSmallest(root *TreeNode, k int) int {
	if root == nil {
		return 0
	}
	res = 0
	c = 0
	dfs(root, k)
	return res
}

//利用儿茶搜索树的特性 直接终须遍历 病记录遍历次数和速出结果即可 时间复杂度为O(n)
func dfs(root *TreeNode, k int) int {
	if root == nil {
		return 0
	}
	dfs(root.Left, k)
	c++
	if k == c {
		res = root.Val
		return root.Val
	}
	dfs(root.Right, k)
	return 0
}
